The Internet Protocol (“IP”) is an addressing protocol designed to facilitate the routing of traffic within a network or between networks. The Internet Protocol is used on many computer networks including the Internet, intranets and other networks. Current versions of Internet Protocol such as Internet Protocol version-4 (“IPv4”) are becoming obsolete because of limited address space. With a 32-bit address-field, it is possible to assign 232 different addresses, which is 4,294,967,296, or greater than about 4 billion globally unique addresses.
However, with the explosive growth of the Internet and intranets, Internet Protocol addresses using a 32-bit address-field may soon be exhausted. Internet Protocol version-6 (“IPv6”) proposes the use of a 128-bit address-field for Internet Protocol addresses. However, a large number of legacy networks including a large number of Internet subnets, will still be using older versions for Internet Protocol with a 32-bit address space for many years to come. As is known in the art, a subnet is smaller of part of a larger network using a similar network addressing scheme.
Network Address Translation (“NAT”) has been proposed to extend the lifetime of Internet Protocol version 4 by allowing subnets with private Internet Protocol addresses to exist behind a single or small number of globally unique Internet Protocol addresses (see e.g., Internet Engineering Task Force (“IETF”) RFC-2663, “IP Network Address Translator (“NAT”) Terminology and Considerations,” by P. Srisuresh and M. Holdrege, August 1999). Each private host uses a single global Internet Protocol address for communication with external networks such as the Internet.
Internally, a subnet may use local private addressing. Local private addressing may be any addressing scheme that is different from the public Internet Protocol addressing. The local addresses on a subnet are typically not available to the external, global Internet. When a device or node using local addressing desires to communicate with the external world, its local address is translated to a common external Internet Protocol address used for communication with an external network by a network address translation device. That is, network address translation allows one or more global Internet Protocol addresses to be shared among a larger number of network devices using local private addresses.
There are several problems associated with using network address translation to extend the life of the Internet Protocol version-4. Network address translation interferes with the end-to-end routing principal of the Internet that recommends that packets flow end-to-end between network devices without changing the contents of any packet along a transmission route (see e.g., “Routing in the Internet,” by C. Huitema, Prentice Hall, 1995, ISBN 0-131-321-927).
Current versions of network address translation replace a local network address in a data packet header with an external global network address on outbound traffic, and replace an external global network address in a data packet header with a local private network address on inbound traffic. This type of address translation is computationally expensive, causes security problems by preventing certain types of encryption from being used, or breaks a number of existing applications in a network that cannot coexist with network address translation (e.g., File Transfer Protocol (“FTP”)).
Current versions of network address translation may not gracefully scale beyond a small subnet containing a few dozen nodes or devices because of the computational and other resources required. Network address translation potentially requires support for many different application layer internal network protocols be specifically programmed into a translation mechanism such as a network address translation router.
Computational burdens placed on a network address translation router may be significant and degrade network performance, especially if several network address translation-enabled sub-networks share the same network address translation router. In a worst case scenario, a network address translation router translates every inbound and data packet.
Some of the problems associated with network address translation of private network addresses into public network addresses have been overcome with Distributed Network Address Translation (“DNAT’) and “Realm Specific Internet Protocol” (“RSIP”) as is explained below.
The Internet Protocol is used on global computer networks such as the Internet, and on many private networks such as intranets and Virtual Private Networks. It is often desirable to protect information sent with the Internet Protocol using different types of security. Using security with the Internet Protocol allows private or sensitive information to be sent over a public network with some degree of confidence that the private or sensitive information will not be intercepted, examined or altered.
Internet Protocol security (“IPsec”) is a protocol for implementing security for communications on networks using the Internet Protocol through the use of cryptographic key management procedures and protocols. Communications between two endpoints of an Internet Protocol traffic flow are made end-to-end-secure by the Internet Protocol security protocol on an individual Internet Protocol packet-by-packet basis. Internet Protocol security protocol entities at connection endpoints have access to, and participate in, critical and sensitive operations that make a common connection secure.
The Internet Key Exchange (“IKE”) protocol establishes a secure Internet Protocol security channel between two network devices. In order to avoid “denial-of-service” attacks, Internet Key Exchange enabled network devices that perform Diffie and Hellman exponentiation, use anti-clogging digital “tokens” or “cookies”. As is known in the art, a digital “cookie” or a digital token is a block of data used to identify a network device or a user of a network device. As is known in the art, Diffie and Hellman (hereinafter Diffie-Hellman) describe a means for two parties to agree upon a shared secret in such a way that the secret will be unavailable to eavesdroppers.
As is known in the art, a “denial-of-service attack” includes flooding a network device with a large number of bogus data packets (e.g., flooding a network device with bogus data packets including bogus Internet Protocol source addresses). Absolute protection against denial of service is virtually impossible, but anti-clogging digital cookies provide a technique for reducing the impact of denial-of-service attacks.
Anti-clogging digital cookies are used in Internet Key Exchange protocol exchanges between an initiator and a responder. The details of anti-clogging digital cookie generation are implementation dependant, but should satisfy the three basic requirements of digital cookie generation stated by Phil Karn as is presented in “Internet Security Association and Key Management Protocol (“ISAKMP”),” by D. Maughan, M. Schertler, M. Schneider and J. Turner, IETF RFC-2408, November, 1998. See also P. Karn and W. Simpson in “Photuris: Session Key Management Protocol,” IETF RFC-2522, March 1999.
These three basic requirements of digital cookie generation include: (1) The digital cookie must depend on the specific parties using the digital cookie. This prevents an attacker from obtaining a digital cookie using a real Internet Protocol address and User Datagram Protocol (“UDP”) port, and then using it to swamp the victim with Diffie-Hellman requests from randomly chosen Internet Protocol addresses or User Datagram Ports; (2) It must not be possible for anyone other than an issuing entity to generate digital cookies that will be accepted by that entity. This implies that the issuing entity must use local secret information in the generation and subsequent verification of a digital cookie. It must not be possible to deduce this secret information from any particular digital cookie; and (3) The digital cookie generation function must be fast enough to thwart attacks intended to sabotage Central Processing Unit resources.
In subnets that utilize an Internet Protocol address sharing scheme such as Distributed Network Address Translation or Realm Specific Internet Protocol, a digital cookie is used by a Distributed Network Address Translation/Realm Specific Internet Protocol gateway to route responses. If Internet Key Exchange protocol is used (e.g., source port 500), all digital cookies must be unique to allow for routing to an appropriate network device. Thus, all initiator digital cookies in use on a given DNAT/RSIP subnet must be unique.
There are a number of methods used to create anti-clogging digital cookies. For example, an initiator randomly chooses a digital cookie and transmits the digital cookie in a first Internet Key Exchange protocol message. A gateway to a subnet examines the digital cookie, and if it matches any other digital cookie in use, the gateway either: (a) drops the message; or (b) sends an error message back to the initiator. The problem with this method is that the multiple messages add latency to the Internet Key Exchange protocol transactions, or require modifications to the Internet Key Exchange protocol.
Another method to create an anti-clogging digital cookie includes allowing a gateway to allocate contiguous blocks of digital cookies to each initiator. A initiator can randomly choose digital cookies within the space of their given block of digital cookies. The problem is that this method reduces the entropy of the digital cookies on a per client basis from x-bits (e.g., 64 bits for Internet Protocol Exchange digital cookies) to something less than x-bits, and therefore violates digital cookie generation requirement (2) stated above.
A number of distributed and parallel random number generation methods have been proposed that may be used generate digital cookies or digital tokens. However, many of these methods rely on parallelizing random generation using multiple parallel processsors. See for example, U.S. Pat. No. 5,793,657, “Random number generating apparatus and random number generating method in a multiprocessor system,” U.S. Pat. No. 5,327,365, “Generating system of random-number sequences for a parallel computer system,” at the Universal Resource Location (“URL”), http://www-unix.mcs.anl.gov/dbpp/text/node116.html Section 10, “Designing and Building Parallel Programs,” by Ian Foster, 1995, at the URL, http://csep1.phy.orn1.gov/rn/node19.html#SECTION00060000000000000000, Section on random number generation, “Vectorization and Access via Multiple Processors: LCGs,” Computational Science Education Project, Sponsored by U.S. Department of Energy, September, 1995.
However, these methods rely on the mathematical properties of the actual parallelized random number generators in use. These methods can not typically be generally deployed on a computer network without specialized parallel processing equipment. These methods may also not produce a unique random number, which is typically required for digital cookie used for security purposes.
Thus, it is desirable to have a digital cookie generation method allows all x-bits of a digital cookie to be generated in a pseudo-random, but non-predictable fashion. The digital cookies should be generated in a manner such that no two digital cookies used by initiators are exactly the same and no two identical digital cookies are in use at the same time on a computer network.